/**
 * 
 */
package leetCode;

import java.util.List;

/**
 * @author zhongfang
 *
 */
public class ShoppingOffers {
    public int shoppingOffers(List<Integer> price, List<List<Integer>> special, List<Integer> needs) {
    	int spN=special.size();
    	int N=price.size();//商品数
    	int[] you=new int[special.size()];
    	int[] count=new int[spN];
    	int[] total=new int[spN];
    	for (int i = 0; i < you.length; i++) {
    		int sum=0;
    		boolean can=true;
    		int minCount=Integer.MAX_VALUE;
			for (int j = 0; j < N; j++) {
				if(special.get(i).get(j)<=needs.get(j)){//第j个商品不超过需求
					sum+=price.get(j)*special.get(i).get(j);
                    if(special.get(i).get(j)!=0)
					minCount=Math.min(minCount, needs.get(j)/special.get(i).get(j));
				}else {
					can =false;
					break;
				}
			}
			if(can){
				you[i]=sum-special.get(i).get(N);
				count[i]=minCount;
				total[i]=you[i]*count[i];
			}else {
				you[i]=-1;
			}
		}
    	int original=0;
    	for (int i = 0; i < N; i++) {
			original+=price.get(i)*needs.get(i);
		}
    	boolean usable=true;
    	while (usable) {
			usable=false;//有可用的优惠
			int maxYou=0;
			int maxIndex=-1;
			for (int i = 0; i < spN; i++) {//最大能用的优惠
				boolean use=true;
				for (int j = 0; j < N; j++) {//能用——需求>=使用
					if(special.get(i).get(j)>needs.get(j)){//第j个商品不超过需求
						use=false;
					}
				}
				if(use){
					if(maxYou<you[i]){
						maxIndex=i;
						maxYou=you[i];
					}
					usable=true;
				}
			}
			if(usable){
				original-=maxYou;
				//修改需求
				for (int j = 0; j < N; j++) {
					needs.set(j,needs.get(j)-special.get(maxIndex).get(j));
				}
			}
		}
        return original;        
    }
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
